package com.leetcode;

import com.leetcode.common.ListNode;
import static com.leetcode.util.LinkedListUtil.printList;

/**
 * 23. 合并K个升序链表
 * 考虑优化方法一，用分治的方法进行合并
 */
public class Solution23 {

    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int l, int r) {
        // fix k个列表都是null的情况
        if (l > r) {
            return null;
        }
        if (l == r) {
            return lists[l];
        }
//        int mid = l + ((r - l) >> 1);
        int mid = l + (r - l) / 2;
        return mergeTwoList(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    private ListNode mergeTwoList(ListNode a, ListNode b) {
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }
        ListNode head = new ListNode(0);
        ListNode cur = head;
        ListNode aCur = a;
        ListNode bCur = b;
        while (aCur != null && bCur != null) {
            if (aCur.val < bCur.val) {
                cur.next = aCur;
                aCur = aCur.next;
            } else {
                cur.next = bCur;
                bCur = bCur.next;
            }
            cur = cur.next;
        }
        cur.next = aCur != null ? aCur : bCur;
        return head.next;
    }

    public static void main(String[] args) {
        ListNode res = new Solution23().mergeKLists(new ListNode[]{});
        printList(res);
    }

}
